package com.hyper_yang.algorithmRecord;

import java.util.HashMap;

// least recently used cache 自定义实现 HashMap + 双向链表
public class LRUCache {
    /*
    请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
    实现 LRUCache 类：
    LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
    int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
     */
    // 定义双向链表的节点类
    class Node {
        int key;
        int value;
        Node next;
        Node prev;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 定义哈希表
    private HashMap<Integer, Node> hashMap = new HashMap<>();
    // 基本属性
    private int capacity; // capacity: 总容量
    private int size; // size: 占用容量  size <= capacity
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;

        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // 从哈希表中查找
        Node node = hashMap.get(key);
        if (node == null) return -1;

        // 如果存在，将节点移到链表末尾
        moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 从哈希表中查找
        Node node = hashMap.get(key);
        // 如果存在，修改 value，并移到末尾
        if (node != null) {
            node.value = value;
            moveToTail(node);
        }
        // 如果不存在，需要创建新的节点，插入到末尾
        else {
            Node newNode = new Node(key, value);
            hashMap.put(key, newNode); // 存入hashTable
            addToTail(newNode); // 添加到双向链表末尾
            size++;

            // 如果超出了容量限制，删除链表头节点
            if (size > capacity) {
                Node head = removeHead();
                hashMap.remove(head.key);
                size--;
            }
        }
    }

    // 移动到末尾
    private void moveToTail(Node node) {
        removeNode(node);
        addToTail(node);
    }

    // 删除链表中某一节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 链表末尾增加节点
    private void addToTail(Node node) {
        node.next = tail;
        node.prev = tail.prev;
        tail.prev.next =node;
        tail.prev = node;
    }
    // 删除头节点
    private Node removeHead(){
        Node realHead = head.next;
        removeNode(realHead);
        return realHead;
    }
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
    }
}
